package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/3 20:08
 * @Version 1.0
 **/
public class RotateList {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        ListNode p = head, tail, q, pre =head;
        // 先找到链表长度以及尾节点
        int len = 1;
        while (p.next != null) {
            p = p.next;
            len++;
        }
        tail = p;

        k %= len;
        if (k == 0) {
            return head;
        }
        // 找到旋转之后新链表的头节点
        k = len - k + 1;
        p = head;
        while (p.next != null && k > 1) {
            pre = p;
            p = p.next;
            k--;
        }
        // 令新链表的头节点的前继节点的后节点为null, 排除前继节点为本身的情况 【断开操作】
        if (pre != p) {
            pre.next = null;
        }

        // 令尾节点连接到原来的头节点，组成新的链表  【连接操作】
        tail.next = head;
        return p;
    }
}
